import javafx.css.StyleableIntegerProperty;

import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.Map;

class LRUCache146 {
    public static void main(String[] args) {
        LRUCache146 lruCache146 = new LRUCache146(2);
        lruCache146.put(2,1);
        lruCache146.put(1,1);
        lruCache146.put(2,3);
        lruCache146.put(4,1);
        System.out.println(lruCache146.get(1));
        System.out.println(lruCache146.get(2));
    }
    class Node{
        private int val ;
        private int key ;
        private Node next ;
        private Node prev ;
        public Node(){
        }
        public Node(int key , int val){
            this.val = val;
            this.key = key ;
        }

    }
    private Map<Integer , Node> hash ;
    private int maxSize ;
    private Node head ;
    private Node end ;

    public LRUCache146(int capacity) {
          this.maxSize = capacity ;
          hash = new HashMap<>();
          head = new Node();
          end = head ;
    }

    public int get(int key) {
        Node tmp = hash.getOrDefault(key , null);
        if(tmp == null){
            return -1 ;
        }
        if(tmp.next != null){
            tmp.next.prev = tmp.prev ;
            tmp.prev.next = tmp.next ;
            tmp.prev = end ;
            end.next = tmp ;
            tmp.next = null ;
            end = tmp ;
        }
        return tmp.val;
    }

    public void put(int key, int value) {
        addNode(key , value);
    }
    private void addNode(int key , int value){
          if(hash.containsKey(key)){
              Node node = hash.get(key) ;
              node.val = value ;
              if(node.next != null){
                  node.next.prev = node.prev ;
                  node.prev.next = node.next ;
                  node.prev = end ;
                  end.next = node ;
                  node.next = null ;
                  end = node ;
              }
          }else{
              Node node = new Node(key , value);
              node.prev = end ;
              end.next = node ;
              end = node ;
              hash.put(key , node) ;
              if(hash.size() > maxSize){
                  Node out = head.next ;
                  out.next.prev = head;
                  head.next = out.next ;
                  hash.remove(out.key) ;
              }
          }

    }

}
